package sorting

import "gitee.com/guuzaa/sorting/constraints"

func RadixSort[T constraints.Unsigned](arr []T) []T {
	if len(arr) < 2 {
		return arr
	}

	max := arr[0]
	for _, n := range arr {
		if max < n {
			max = n
		}
	}

	for exp := 1; max/T(exp) > 0; exp *= 10 {
		countSort(arr, T(exp))
	}

	return arr
}

func countSort[T constraints.Unsigned](arr []T, exp T) {
	n := len(arr)
	output := make([]T, n)
	count := make([]int, 10)

	for i := 0; i < n; i++ {
		count[(arr[i]/exp)%10]++
	}

	for i := 1; i < 10; i++ {
		count[i] += count[i-1]
	}

	for i := n - 1; i >= 0; i-- {
		output[count[(arr[i]/exp)%10]-1] = arr[i]
		count[(arr[i]/exp)%10]--
	}

	for i := 0; i < n; i++ {
		arr[i] = output[i]
	}
}
